package sort.LeetCode;
//148. 排序链表


//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

public class Num148_sortList {
    //递归写法，超出了时间限制
/*    public static ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        head.next = sortList(head.next);
        if(head.val < head.next.val){
            return head;
        }else{
            ListNode dymuuhead = head.next;
            ListNode prve = head;
            int val = head.val;
            for (ListNode x = head.next; x != null ;) {
                    if(x.val > val){
                        prve.next = head;
                        head.next = x;
                        break;
                    }
                x = x.next;
                prve = prve.next;
                if(x == null){
                    prve.next = head;
                    head.next = x;
                }
            }
            return dymuuhead;
        }

    }*/
            //用归并写法试试看
/*

    public static ListNode sortList(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }
        ListNode min = middleLinked(head);//找到链表中的中间节点
        ListNode tmp = min.next;//中间节点的下一个节点位置
        min.next = null;//分割两个链表，断开连接
        ListNode left = sortList(head);//左链表头节点
        ListNode right = sortList(tmp);//右链表头节点


        //现在左右链表已经排序好了，合并就可以了
        ListNode cur = new ListNode(0);//创建一个新链表的头，用来串联
        ListNode dummyHead = cur;//链表永远的头节点前驱，不动。
        while(left != null && right != null){

            if(left.val < right.val){
                cur.next = left;
                left = left.next;
            }else{
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        //判断没走完的链表
        cur.next = left != null ? left : right;

        return dummyHead.next;
    }

    */

    /**
     * 传入链表头节点，然后链表的中间节点
     *//*

    public static ListNode middleLinked(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;//因为我们要的是偶数中间的前面一个

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
*/


    public static void main(String[] args) {
        int[] arr = {4,2,1,3};
        ListNode head = add(arr);
        System.out.println(day(head));

        head = sortList(head);
        System.out.println(head.val);
        System.out.println(day(head));
    }


 //自己再写一遍
    public static ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode low = head;
        ListNode fast = head.next;//如果是偶数的话要取中间节点的前面一个
        while(fast != null && fast.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        ListNode tmp = low.next;//保存中间节点下一个节点地址
        low.next = null;//断开两个链表的连接

        ListNode left = sortList(head);//保存左链表节点地址
        ListNode right = sortList(tmp);//保存右链表节点地址


        //最后由我们合并这个大的链表
        ListNode prve = new ListNode(-1);//前驱
        ListNode dummyHead = prve;//永远的头节点

        while(left != null && right != null){
            if(left.val <= right.val){
                prve.next = left;
                left = left.next;
            }else{
                prve.next = right;
                right = right.next;
            }
            prve = prve.next;
        }
        //判断是否还有链表没走完
        prve.next = left == null ? right : left;

        return dummyHead.next;
    }





    //根据给整形数组创建一个相同的链表并返回
    public static ListNode add(int[] arr){
         ListNode head = new ListNode();
         ListNode prve = head;

        for (int i = 0; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            prve.next = node;
            prve = node;
        }
        return head.next;
    }

    //打印链表方法
    public static String day(ListNode head){
        String rep = "";
        //一定要创建一个变量来变量，如果直接用
        //head来变量的话就丢失原来的地址，找不到头节点了
        for (ListNode x = head; x != null ; x = x.next) {
            //走到尾节点为null地址算结束
            rep += x.val;
            rep += " -> ";
        }
        rep += "NULL";//用来表示链表走到空了
        return rep;
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}